package god.day03;

import java.util.Arrays;

/**
 * @author wang hao
 * @date 2023-02-19 12:10
 *
 *      求逆序对个数
 */
public class Demo03 {
    public static int res = 0;

    public static void main(String[] args) {
        int[] arr = new int[]{7,5,6,4};
        int i = Demo03.reversePairs(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println(i);
    }

    public static int reversePairs(int[] nums) {
        if (nums == null && nums.length < 2){
            return 0;
        }
        sort(nums, 0, nums.length -1);
        return res;
    }

    private static int sort(int[] nums, int l, int r) {
        if (l >= r) return 0;
        int mid = l + ((r - l) >> 1);
        sort(nums, l, mid);
        sort(nums, mid + 1, r);
        merge(nums, l, mid, r);
        return res;
    }

    private static int merge(int[] arr, int l, int mid, int r) {
        int help[] = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;


        while (p1 <= mid && p2 <= r){
            if (arr[p1] > arr[p2]){
                res += mid - p1 + 1; //  3,4   1,2  3 比 1 大 说明 arr[p1] > arr[p2]  说明3和3右边的数逗比1大 mid-p1+1
                help[i] = arr[p2];
                i++;
                p2++;
            }else  {
                help[i] = arr[p1];
                i++;
                p1++;
            }
        }

        while (p1 <= mid){
            help[i++] = arr[p1++];
        }

        while (p2 <= r){
            help[i++] = arr[p2++];
        }


        for (int j = 0; j < help.length; j++) {
            arr[l + j] = help[j];
        }
        return res;

    }

}
